package com.winning.hashmap;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Hao.Y
 * @param <K>
 * @param <V>
 */
public class MyHashMap<K, V> implements MyMap<K, V> {

    //数组初始化长度
    private static final int DEFAULT_INITAL_CAPACTIY = 1 << 4;
    //负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private int defaultInitSize;

    private float defaultLoadFactor;

    //Map中Entry的数量
    private int entryUseSize;

    private Entry<K, V>[] table = null;

    public MyHashMap(){
        this(DEFAULT_INITAL_CAPACTIY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int defaultInitSize, float defaultLoadFactor){

        if(defaultInitSize < 0){
            throw new IllegalArgumentException("参数异常：" + defaultInitSize);
        }

        if(defaultLoadFactor < 0){
            throw new IllegalArgumentException("参数异常：" + defaultLoadFactor);
        }

        this.defaultInitSize = defaultInitSize;
        this.defaultLoadFactor = defaultLoadFactor;

        table = new Entry[this.defaultInitSize];
    }


    @Override
    public V put(K k, V v) {

        //数组下标
        int index = calcuIndex(k);

        if(table[index] == null){
            table[index] = new Entry<K, V>(k, v, null);
            ++ entryUseSize;
        }else{
            Entry<K, V> entry = table[index];
            Entry<K, V> e = entry;

            while(e != null){
                if(k == e.key || k.equals(e.key)){
                    V oldValue = e.value;
                    e.value = v;
                    return oldValue;
                }

                e = e.next;
            }

            //在链表的最后一位添加一个新的节点
            e.next = new Entry<K, V>(k, v, null);
            //扩容
            if(++ entryUseSize >= defaultInitSize * defaultLoadFactor){
                resize();
            }
        }
        return null;
    }

    /**
     * 计算数组下标
     * @param k
     * @return
     */
    private int calcuIndex(K k) {
        int n;
        //如果 key 为null，则 hash = 0，
        //否则用 key 的 hashCode 的高16位和低16位进行亦或
        int hash = k == null ? 0 : (n = k.hashCode()) ^ (n >>> 16);

        //计算数组下标
        return hash & (defaultInitSize - 1);
    }

    /**
     * 扩容
     */
    private void resize() {
        defaultInitSize = defaultInitSize << 1;
        Entry<K, V>[] newTable = new Entry[defaultInitSize];
        entryUseSize = 0;
        rehash(newTable);

    }

    /**
     * 重新构造数组和链表
     * @param newTable
     */
    private void rehash(Entry<K,V>[] newTable) {

        //得到原来老的Entry集合，注意遍历单链表
        List<Entry<K, V>> entryList = new ArrayList<>();
        for(Entry<K, V> entry : table){
            if(entry != null){
                do{
                    entryList.add(entry);
                    entry = entry.next;
                }while(entry != null);
            }
        }

        if(newTable.length > 0){
            table = newTable;
        }

        for(Entry<K, V> entry : entryList){
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public V get(K k) {
        //数组下标
        int index = calcuIndex(k);
        if(table[index] == null){
            return null;
        }else{
            Entry<K, V> entry = table[index];
            do{
                if(k == entry.getKey() || k.equals(entry.key)){
                    entryUseSize --;
                    return entry.getValue();
                }
                entry = entry.next;
            }while (entry != null);
        }
        return null;
    }

    class Entry<K, V> implements MyMap.Entry<K, V>{

        private K key;
        private V value;
        private Entry<K, V> next;

        public Entry(){

        }

        public Entry(K key, V value, Entry<K, V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }
    }
}




